package problem.year2021.february;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 中位数是有序序列最中间的那个数。如果序列的大小是偶数，则没有最中间的数；此时中位数是最中间的两个数的平均数。
 * <p>
 * 例如：
 * <p>
 * [2,3,4]，中位数是 3
 * [2,3]，中位数是 (2 + 3) / 2 = 2.5
 * <p>
 * 给你一个数组 nums，有一个大小为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数，每次窗口向右移动 1 位。你的任务是找出每次窗口移动后得到的新窗口
 * 中元素的中位数，并输出由它们组成的数组。
 * <p>
 * 示例：
 * <p>
 * 给出 nums = [1,3,-1,-3,5,3,6,7]，以及 k = 3。
 * <p>
 * 窗口位置                      中位数
 * ---------------               -----
 * [1  3  -1] -3  5  3  6  7       1
 * 1 [3  -1  -3] 5  3  6  7      -1
 * 1  3 [-1  -3  5] 3  6  7      -1
 * 1  3  -1 [-3  5  3] 6  7       3
 * 1  3  -1  -3 [5  3  6] 7       5
 * 1  3  -1  -3  5 [3  6  7]      6
 * <p>
 * 因此，返回该滑动窗口的中位数数组 [1,-1,-1,3,5,6]。
 * <p>
 * 提示：
 * <p>
 * 你可以假设 k 始终有效，即：k 始终小于输入的非空数组的元素个数。
 * 与真实值误差在 10 ^ -5 以内的答案将被视作正确答案。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/sliding-window-median
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class February3 {
    static class Solution {
        public double[] medianSlidingWindow(int[] nums, int k) {
            if (k==1) {
                double[] res = new double[nums.length];
                for (int i = 0; i < nums.length; ++i) {
                    res[i] = (double) nums[i];
                }
                return res;
            }
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < k; ++i) {
                list.add(nums[i]);
            }
            Collections.sort(list);
            SlidingWindow slidingWindow = new SlidingWindow(k, list);
            double[] doubles = new double[nums.length - k + 1];
            for (int i = k; i < nums.length; ++i) {
                doubles[i-k] = slidingWindow.findMedian();
                slidingWindow.insertTail(nums[i]);
            }
            return doubles;
        }

        private class SlidingWindow {
            List<Integer> list;
            int k;

            public SlidingWindow(int k, List<Integer> list) {
                this.k = k;
                this.list = list;
            }

            // 对已经排好序列的数组插入一个数字
            private void insertAndSort(int value) {
                for (int i = 0; i < k; ++i) {
                    if (value <= list.get(i)) {
                        list.add(i, value);
                        return;
                    }
                }
                list.add(value);
            }

            public void insertTail(int value) {
                list.remove(0);
                insertAndSort(value);
            }

            public double findMedian() {
                if (k % 2 == 1) return list.get(k / 2);
                return (double) (list.get(k / 2) + list.get(k / 2 - 1)) / 2;
            }
        }
    }
}
